DP J
The problem of finding the time required to reach the end state by repeating stochastic transitions
The state is the domain of definition and the expected time required is the value Expected DP. If the problem deals with a column of some kind, and replacing any element in the column does not affect the problem, the ordered column is not necessary for the problem.
When the column length is N and the value range is M, M^N in ordered
If you take away the order, you get multiset, and you can have N^M since you can have the number of pieces per value. In the case of this problem, there are 100 things that take 4 different values, so if we do it naively, it's 4^100, but this becomes 100^4, which is much narrower.
The problem of finding the expected value of the time to reach a certain end state when the so-called "probability distribution", with the state as the domain of definition and probability as the value, changes to another distribution with stochastic transitions in a single step of operation.
Instead of simply repeating the update of one step, the DP has an "expected time to reach the end state" as a value, and the expected value of the start state is obtained by calculating from the fact that the value is 0 in the end state.
A simpler question is, "Given four stepping stones, with a 1/2 chance of moving on to the next stone, what is the expected time to reach the goal?" Consider the following
https://gyazo.com/baf9dfe526c87ec53abf6f66fa139c33
Consider a DP that values the expected value of time required
One step after a, we are at 1/2 a and 1/2 b.
Multiply the probabilities and add them together to get "the expected value after one step of a."
A appears on both sides of the equation.
Because it has a 1/2 chance of self-transitioning.
To put things in perspective, we get an expression for a from b
Transitions in this issue
https://gyazo.com/378d95d81f847f835f305597f00c264f
12 TLE when implemented naively.
code:python
def solve(N, AS):
"void()"
from collections import Counter
count = Counter(AS)
expect = {}
def f(a, b, c):
if (a, b, c) in expect:
p = 1.0
if a > 0:
p += f(a - 1, b, c) * a / N
if b > 0:
p += f(a + 1, b - 1, c) * b / N
if c > 0:
p += f(a, b + 1, c - 1) * c / N
p *= N / (a + b + c)
# debug("f: a,b,c,p", a, b, c, p)
return p
return f(count1, count2, count3) Slightly rewritten AC
code:python
def solve(N, AS):
from collections import Counter
count = Counter(AS)
expect = [[-1 * (N + 1) for i in range(N + 1)] for j in range(N + 1)] def f(a, b, c):
p = N
if a > 0:
if v == -1:
v = f(a - 1, b, c)
p += v * a
if b > 0:
if v == -1:
v = f(a + 1, b - 1, c)
p += v * b
if c > 0:
if v == -1:
v = f(a, b + 1, c - 1)
p += v * c
p /= (a + b + c)
# debug("f: a,b,c,p", a, b, c, p)
return p
return f(count1, count2, count3) ---
This page is auto-translated from /nishio/DP J. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.